home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1 Issue 2 / PDCD-1 - Issue 02.iso / _utilities / utilities / 003 / _gs / !GS / c / GXSTROKE < prev    next >
Text File  |  1991-10-26  |  23KB  |  703 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gxstroke.c */
  21. /* Path stroking procedures for Ghostscript library */
  22. #include "math_.h"
  23. #include "gx.h"
  24. #include "gserrors.h"
  25. #include "gxfixed.h"
  26. #include "gxarith.h"
  27. #include "gxmatrix.h"
  28. #include "gzstate.h"
  29. #include "gzdevice.h"
  30. #include "gzcolor.h"            /* requires gxdevice.h */
  31. #include "gzline.h"
  32. #include "gzpath.h"
  33.  
  34. /* stroke_add uses the following global for its path: */
  35. private gx_path stroke_path_body;
  36. private gx_path *stroke_path;
  37.  
  38. /*
  39.  * Structure for a partial line (passed to the drawing routine).
  40.  * Two of these are required to do joins right.
  41.  * Each endpoint includes the two ends of the cap as well,
  42.  * and the deltas for square and round cap computation.
  43.  *
  44.  * The deltas (co, ce, cdelta) are in clockwise order in device space
  45.  * around the endpoint p: they are one-half the line width (suitably
  46.  * transformed) at 90 degrees counter-clockwise, straight ahead,
  47.  * and 90 degrees from the oriented line o->e, where "90 degrees"
  48.  * is measured in *user* coordinates.
  49.  * Note that the values at o are the negatives of the values at e.
  50.  *
  51.  * Initially, only o/e.p, o.cdelta, width, and thin are set.
  52.  * compute_caps fills in the rest when needed.
  53.  */
  54. typedef gs_fixed_point _ss *p_ptr;
  55. typedef struct endpoint_s {
  56.     gs_fixed_point p;        /* the end of the line */
  57.     gs_fixed_point co, ce;        /* ends of the cap, p +/- width */
  58.     gs_fixed_point cdelta;        /* +/- cap length */
  59. } endpoint;
  60. typedef endpoint _ss *ep_ptr;
  61. typedef struct partial_line_s {
  62.     endpoint o;            /* starting coordinate */
  63.     endpoint e;            /* ending coordinate */
  64.     gs_fixed_point width;        /* one-half line width, see above */
  65.     int thin;            /* true if minimum-width line */
  66. } partial_line;
  67. typedef partial_line _ss *pl_ptr;
  68.  
  69. /* Procedures that stroke a partial_line (the first argument). */
  70. /* If both partial_lines are non-null, the procedure creates */
  71. /* an appropriate join; otherwise, the procedure creates an */
  72. /* end cap.  If the first int is 0, the procedure also starts with */
  73. /* an appropriate cap. */
  74. private int stroke_add(P4(int, pl_ptr, pl_ptr, gs_state *));
  75. private int stroke_fill(P4(int, pl_ptr, pl_ptr, gs_state *));
  76.  
  77. /* Other forward declarations */
  78. private int stroke(P3(gx_path *,
  79.   int (*)(P4(int, pl_ptr, pl_ptr, gs_state *)),
  80.   gs_state *));
  81. private int expand_dashes(P3(subpath *, gx_path *, gs_state *));
  82. private void compute_caps(P1(pl_ptr));
  83. private int add_capped(P4(gx_path *, gs_line_cap,
  84.   int (*)(P3(gx_path *, fixed, fixed)),
  85.   ep_ptr));
  86.  
  87. /* Stroke a path for drawing or saving */
  88. int
  89. gx_stroke_fill(gx_path *ppath, gs_state *pgs)
  90. {    int code;
  91.     stroke_path = 0;
  92.     code = stroke(ppath, stroke_fill, pgs);
  93.     if ( stroke_path )        /* set if filling needed */
  94.       { if ( code >= 0 )
  95.           code = gx_fill_path(stroke_path, pgs->dev_color, pgs,
  96.                   gx_rule_winding_number, (fixed)0);
  97.         gx_path_release(stroke_path);
  98.       }
  99.     return code;
  100. }
  101. int
  102. gx_stroke_add(gx_path *ppath, gx_path *topath, gs_state *pgs)
  103. {    stroke_path = topath;
  104.     return stroke(ppath, stroke_add, pgs);
  105. }
  106.  
  107. /* Stroke a path.  Call line_proc (stroke_add or stroke_fill) */
  108. /* for each line segment. */
  109. private int
  110. stroke(gx_path *ppath,
  111.   int (*line_proc)(P4(int, pl_ptr, pl_ptr, gs_state *)),
  112.   gs_state *pgs)
  113. {    subpath *psub;
  114.     subpath *save_psub = 0;
  115.     int code = 0;
  116.     line_params *lp = pgs->line_params;
  117.     int dash_count = lp->dash.pattern_size;
  118.     gx_path fpath, dpath;
  119.     float xx = pgs->ctm.xx, xy = pgs->ctm.xy;
  120.     float yx = pgs->ctm.yx, yy = pgs->ctm.yy;
  121.     int skewed = !is_fzero2(xy, yx);
  122.     int uniform = (skewed ? 0 : xx == yy ? 1 : xx == -yy ? -1 : 0);
  123.     /*
  124.      * We are dealing with a reflected coordinate system
  125.      * if (1,0) is counter-clockwise from (0,1).
  126.      * See the note in stroke_add for the algorithm.
  127.      */    
  128.     int reflected =
  129.       (uniform ? uniform < 0 :
  130.        skewed ? xy * yx < xx * yy :
  131.        (xx < 0) == (yy < 0));
  132.     float line_width = lp->width;
  133.     int always_thin;
  134.     float line_width_and_scale;
  135. #ifdef DEBUG
  136. if ( gs_debug['o'] )
  137.    {    int count = lp->dash.pattern_size;
  138.     int i;
  139.     dprintf3("[o]half_width=%f, cap=%d, join=%d,\n",
  140.          lp->width, (int)lp->cap, (int)lp->join);
  141.     dprintf2("   miter_limit=%f, miter_check=%f,\n",
  142.          lp->miter_limit, lp->miter_check);
  143.     dprintf1("   dash pattern=%d", count);
  144.     for ( i = 0; i < count; i++ )
  145.         dprintf1(",%f", lp->dash.pattern[i]);
  146.     dprintf4(",\n   offset=%f, init(ink_on=%d, index=%d, dist_left=%f)\n",
  147.          lp->dash.offset, lp->dash.init_ink_on, lp->dash.init_index,
  148.          lp->dash.init_dist_left);
  149.    }
  150. #endif
  151.     if ( line_width < 0 ) line_width = -line_width;
  152.     if ( is_fzero(line_width) )
  153.         always_thin = 1;
  154.     else if ( skewed )
  155.         always_thin = 0;
  156.     else
  157.        {    float xxa = xx, yya = yy;
  158.         if ( xxa < 0 ) xxa = -xxa;
  159.         if ( yya < 0 ) yya = -yya;
  160.         always_thin = (max(xxa, yya) * line_width < 0.75);
  161.        }
  162.     line_width_and_scale = line_width * (float)int2fixed(1);
  163.     /* Start by flattening the path.  We should do this on-the-fly.... */
  164.     if ( !ppath->curve_count )    /* don't need to flatten */
  165.        {    psub = ppath->first_subpath;
  166.         if ( !psub ) return 0;
  167.        }
  168.     else
  169.        {    if ( (code = gx_path_flatten(ppath, &fpath, pgs->flatness)) < 0 ) return code;
  170.         psub = fpath.first_subpath;
  171.        }
  172.     if ( dash_count )
  173.         gx_path_init(&dpath, &ppath->memory_procs);
  174.     for ( ; ; )
  175.      { int segcount;
  176.        line_segment *pline;
  177.        fixed x, y;
  178.        partial_line pl, pl_prev, pl_first;
  179.        int first = 0;
  180.        int index = 0;
  181.        if ( !psub )
  182.         {    /* Might just be the end of a dash expansion. */
  183.         if ( save_psub )
  184.            {    gx_path_release(&dpath);
  185.             psub = (subpath *)save_psub->last->next;
  186.             if ( !psub ) break;
  187.             gx_path_init(&dpath, &ppath->memory_procs);
  188.             save_psub = 0;
  189.            }
  190.         else        /* all done */
  191.             break;
  192.         }
  193.        if ( dash_count && !save_psub )
  194.         {    code = expand_dashes(psub, &dpath, pgs);
  195.         if ( code < 0 ) goto exit;
  196.         save_psub = (subpath *)psub;
  197.         psub = dpath.first_subpath;
  198.         }
  199.        segcount = psub->line_count;        /* no curves left */
  200.        pline = (line_segment *)(psub->next);
  201.        x = psub->pt.x;
  202.        y = psub->pt.y;
  203.        while ( segcount-- )
  204.         {    fixed sx = pline->pt.x;
  205.         fixed sy = pline->pt.y;
  206.         /* Compute the width parameters in device space. */
  207.         /* We work with unscaled values, for speed. */
  208.         fixed udx = sx - x, udy = sy - y;
  209.         pl.o.p.x = x, pl.o.p.y = y;
  210.         pl.e.p.x = sx, pl.e.p.y = sy;
  211.         if ( (udx | udy) || !always_thin )
  212.            {    if ( !(udx | udy) )    /* degenerate */
  213.              { /* Pick an arbitrary orientation */
  214.                udx = int2fixed(1);
  215.              }
  216.             if ( uniform != 0 )
  217.                {    /* We can save a lot of work in this case. */
  218.                 float dpx = udx, dpy = udy;
  219.                 float wl = line_width_and_scale * xx /
  220.                     hypot(dpx, dpy);
  221.                 pl.e.cdelta.x = (fixed)(dpx * wl);
  222.                 pl.e.cdelta.y = (fixed)(dpy * wl);
  223.                 if ( uniform > 0 )    /* xx == yy */
  224.                    {    pl.width.x = pl.e.cdelta.y;
  225.                     pl.width.y = -pl.e.cdelta.x;
  226.                    }
  227.                 else            /* xx == -yy */
  228.                    {    pl.width.x = -pl.e.cdelta.y;
  229.                     pl.width.y = pl.e.cdelta.x;
  230.                    }
  231.                }
  232.             else
  233.                {    gs_point dpt;    /* unscaled */
  234.                 float wl;
  235.                 if ( skewed )
  236.                     gs_idtransform(pgs,
  237.                           (float)udx, (float)udy, &dpt);
  238.                 else    /* shortcut */
  239.                     dpt.x = udx / xx,
  240.                     dpt.y = udy / yy;
  241.                 wl = line_width_and_scale /
  242.                     hypot(dpt.x, dpt.y);
  243.                 /* Construct the width vector in */
  244.                 /* user space, still unscaled. */
  245.                 dpt.x *= wl;
  246.                 dpt.y *= wl;
  247.                 /*
  248.                  * We now compute both perpendicular
  249.                  * and (optionally) parallel half-widths,
  250.                  * as deltas in device space.  We use
  251.                  * a fixed-point, unscaled version of
  252.                  * gs_dtransform.  The second computation
  253.                  * folds in a 90-degree rotation (in user
  254.                  * space, before transforming) in the
  255.                  * direction that corresponds to clockwise
  256.                  * in device space.
  257.                  */
  258.                 pl.e.cdelta.x = (fixed)(dpt.x * xx);
  259.                 pl.e.cdelta.y = (fixed)(dpt.y * yy);
  260.                 if ( skewed )
  261.                   pl.e.cdelta.x += (fixed)(dpt.y * yx),
  262.                   pl.e.cdelta.y += (fixed)(dpt.x * xy);
  263.                 if ( reflected )
  264.                   dpt.x = -dpt.x, dpt.y = -dpt.y;
  265.                 pl.width.x = (fixed)(dpt.y * xx),
  266.                 pl.width.y = -(fixed)(dpt.x * yy);
  267.                 if ( skewed )
  268.                   pl.width.x -= (fixed)(dpt.x * yx),
  269.                   pl.width.y += (fixed)(dpt.y * xy);
  270.                }
  271.             pl.thin =
  272.               any_abs(pl.width.x) + any_abs(pl.width.y) <
  273.                 float2fixed(0.75);
  274.             if ( !pl.thin ) compute_caps(&pl);
  275.            }
  276.         else
  277.             pl.e.cdelta.x = pl.e.cdelta.y = 0,
  278.             pl.width.x = pl.width.y = 0,
  279.             pl.thin = 1;
  280.         if ( first++ == 0 ) pl_first = pl;
  281.         if ( index++ ) (*line_proc)(index - 2, &pl_prev, &pl, pgs);
  282.         pl_prev = pl;
  283.         pline = (line_segment *)(pline->next);
  284.         x = sx, y = sy;
  285.         }
  286.        if ( index )
  287.         {    /* If closed, join back to start, else cap */
  288.         (*line_proc)(index - 1, &pl_prev,
  289.                  (psub->closed ? &pl_first : (pl_ptr)0), pgs);
  290.         }
  291.        psub = (subpath *)pline;
  292.        if ( stroke_path == &stroke_path_body )
  293.         {    /* Fill and release the accumulated path */
  294.         gx_fill_path(stroke_path, pgs->dev_color, pgs,
  295.                  gx_rule_winding_number, (fixed)0);
  296.         gx_path_release(stroke_path);
  297.         stroke_path = 0;
  298.         }
  299.      }
  300. exit:    if ( dash_count ) gx_path_release(&dpath);
  301.     if ( ppath->curve_count ) gx_path_release(&fpath);
  302.     return code;
  303. }
  304.  
  305. /* ------ Internal routines ------ */
  306.  
  307. /* Expand a dashed subpath into explicit segments. */
  308. /* The subpath contains no curves. */
  309. private int
  310. expand_dashes(subpath *psub, gx_path *ppath, gs_state *pgs)
  311. {    int skewed = is_skewed(&pgs->ctm);
  312.     dash_params *dash = &pgs->line_params->dash;
  313.     float *pattern = dash->pattern;
  314.     int count, ink_on, index;
  315.     float dist_left;
  316.     fixed x0 = psub->pt.x, y0 = psub->pt.y;
  317.     fixed x, y;
  318.     segment *pseg;
  319.     int wrap = (dash->init_ink_on && psub->closed ? -1 : 0);
  320.     int drawing = wrap;
  321.     int code;
  322.     if ( (code = gx_path_add_point(ppath, x0, y0)) < 0 )
  323.         return code;
  324.     /* To do the right thing at the beginning of a closed path, */
  325.     /* we have to skip any initial line, and then redo it at */
  326.     /* the end of the path.  Drawing = -1 while skipping, */
  327.     /* 0 while drawing normally, and 1 on the second round. */
  328. top:    count = dash->pattern_size;
  329.     ink_on = dash->init_ink_on;
  330.     index = dash->init_index;
  331.     dist_left = dash->init_dist_left;
  332.     x = x0, y = y0;
  333.     pseg = (segment *)psub;
  334.     while ( (pseg = pseg->next) != 0 && pseg->type != s_start )
  335.        {    fixed sx = pseg->pt.x, sy = pseg->pt.y;
  336.         fixed udx = sx - x, udy = sy - y;
  337.         float length, dx, dy;
  338.         float dist;
  339.         if ( !(udx | udy) )    /* degenerate */
  340.             dx = 0, dy = 0, length = 0;
  341.         else
  342.            {    gs_point d;
  343.             dx = udx, dy = udy;    /* scaled as fixed */
  344.             if ( skewed )
  345.                 gs_idtransform(pgs, dx, dy, &d);
  346.             else    /* shortcut */
  347.                 d.x = dx / pgs->ctm.xx,
  348.                 d.y = dy / pgs->ctm.yy;
  349.             length = sqrt(d.x * d.x + d.y * d.y) *
  350.                    (1 / (float)int2fixed(1));
  351.            }
  352.         dist = length;
  353.         while ( dist > dist_left )
  354.            {    /* We are using up the dash element */
  355.             float fraction = dist_left / length;
  356.             fixed nx = x + (fixed)(dx * fraction);
  357.             fixed ny = y + (fixed)(dy * fraction);
  358.             if ( ink_on )
  359.                {    if ( drawing >= 0 )
  360.                   code = gx_path_add_line(ppath, nx, ny);
  361.                }
  362.             else
  363.                {    if ( drawing > 0 ) return 0;    /* done */
  364.                 code = gx_path_add_point(ppath, nx, ny);
  365.                 drawing = 0;
  366.                }
  367.             if ( code < 0 ) return code;
  368.             dist -= dist_left;
  369.             ink_on = !ink_on;
  370.             if ( ++index == count ) index = 0;
  371.             dist_left = pattern[index];
  372.             x = nx, y = ny;
  373.            }
  374.         dist_left -= dist;
  375.         /* Handle the last dash of a segment. */
  376.         if ( ink_on )
  377.            {    if ( drawing >= 0 )
  378.               code =
  379.                 (pseg->type == s_line_close && drawing > 0 ?
  380.                  gx_path_close_subpath(ppath) :
  381.                  gx_path_add_line(ppath, sx, sy));
  382.            }
  383.         else
  384.            {    if ( drawing > 0 ) return 0;    /* done */
  385.             code = gx_path_add_point(ppath, sx, sy);
  386.             drawing = 0;
  387.            }
  388.         if ( code < 0 ) return code;
  389.         x = sx, y = sy;
  390.        }
  391.     /* Check for wraparound. */
  392.     if ( wrap && drawing <= 0 )
  393.        {    /* We skipped some initial lines. */
  394.         /* Go back and do them now. */
  395.         drawing = 1;
  396.         goto top;
  397.        }
  398.     return 0;
  399. }
  400.  
  401. /* Compute the intersection of two lines.  This is a messy algorithm */
  402. /* that somehow ought to be useful in more places than just here.... */
  403. private void
  404. line_intersect(
  405.     p_ptr pp1,                /* point on 1st line */
  406.     p_ptr pd1,                /* slope of 1st line (dx,dy) */
  407.     p_ptr pp2,                /* point on 2nd line */
  408.     p_ptr pd2,                /* slope of 2nd line */
  409.     p_ptr pi)                /* return intersection here */
  410. {    /* We don't have to do any scaling, the factors all work out right. */
  411.     float u1 = pd1->x, v1 = pd1->y;
  412.     float u2 = pd2->x, v2 = pd2->y;
  413.     double denom = u1 * v2 - u2 * v1;
  414.     double num1 = v1 * pp1->x - u1 * pp1->y;
  415.     double num2 = v2 * pp2->x - u2 * pp2->y;
  416.     double xnum = u1 * num2 - u2 * num1;
  417.     double ynum = v1 * num2 - v2 * num1;
  418.     double max_result = any_abs(denom) * (double)max_fixed;
  419. #ifdef DEBUG
  420. if ( gs_debug['o'] )
  421.    {    dprintf4("[o]Intersect %f,%f(%f/%f)",
  422.          fixed2float(pp1->x), fixed2float(pp1->y),
  423.          fixed2float(pd1->x), fixed2float(pd1->y));
  424.     dprintf4(" & %f,%f(%f/%f),\n",
  425.          fixed2float(pp2->x), fixed2float(pp2->y),
  426.          fixed2float(pd2->x), fixed2float(pd2->y));
  427.     dprintf4("\txnum=%f ynum=%f denom=%f max_result=%f ->\n",
  428.          xnum, ynum, denom, max_result);
  429.    }
  430. #endif
  431.     /* Check for degenerate result. */
  432.     if ( denom == 0 || any_abs(xnum) > max_result || any_abs(ynum) > max_result )
  433.        {    /* The lines are nearly parallel, */
  434.         /* or one of them has zero length.  Punt. */
  435.         *pi = *pp1;
  436. #ifdef DEBUG
  437. if ( gs_debug['o'] )
  438.         dprintf("\tdegenerate!\n");
  439. #endif
  440.        }
  441.     else
  442.        {    pi->x = (fixed)(xnum / denom);
  443.         pi->y = (fixed)(ynum / denom);
  444. #ifdef DEBUG
  445. if ( gs_debug['o'] )
  446.     dprintf2("\t%f,%f\n", fixed2float(pi->x), fixed2float(pi->y));
  447. #endif
  448.        }
  449. }
  450.  
  451. #define lix plp->o.p.x
  452. #define liy plp->o.p.y
  453. #define litox plp->e.p.x
  454. #define litoy plp->e.p.y
  455.  
  456. /* Draw a line on the device. */
  457. private int
  458. stroke_fill(int first, register pl_ptr plp, pl_ptr nplp, gs_state *pgs)
  459. {    if ( plp->thin )
  460.        {    /* Minimum-width line, don't have to be careful. */
  461.         /* We do have to check for the entire line being */
  462.         /* within the clipping rectangle. */
  463.         fixed dx, dy;
  464.         if ( gx_cpath_includes_rectangle(pgs->clip_path,
  465.                 lix, liy, litox, litoy) )
  466.             return gz_draw_line_fixed(lix, liy, litox, litoy,
  467.                 pgs->dev_color, pgs);
  468.         /* We didn't set up the endpoint parameters before, */
  469.         /* because the line was thin.  Do it now. */
  470.         /* We only approximate the width and height. */
  471. #define trsign(v, c) (v < 0 ? c : -c)
  472.         dx = litox - lix, dy = litoy - liy;
  473.         if ( any_abs(dx) > any_abs(dy) )
  474.            {    plp->width.x = plp->e.cdelta.y = 0;
  475.             plp->width.y = -(plp->e.cdelta.x =
  476.                 trsign(dx, float2fixed(0.5)));
  477.            }
  478.         else
  479.            {    plp->width.y = plp->e.cdelta.x = 0;
  480.             plp->width.x = -(plp->e.cdelta.y =
  481.                 trsign(dy, float2fixed(0.5)));
  482.            }
  483. #undef trsign
  484.         compute_caps(plp);
  485.        }
  486.        {    /* General case. */
  487.         /* Construct a path and hand it to the fill algorithm. */
  488.         if ( stroke_path == 0 )
  489.            {    /* We are rendering, and haven't run into the */
  490.             /* general case yet.  Initialize the path. */
  491.             stroke_path = &stroke_path_body;    /* set global for stroke_add */
  492.             gx_path_init(stroke_path, &pgs->memory_procs);
  493.            }
  494.         stroke_add(first, plp, nplp, pgs);
  495.            {    /****** PATCH ******/
  496.             if ( stroke_path == &stroke_path_body )
  497.                {    gx_fill_path(stroke_path, pgs->dev_color, pgs,
  498.                          gx_rule_winding_number, (fixed)0);
  499.                 gx_path_release(stroke_path);
  500.                 stroke_path = 0;
  501.                }
  502.            }
  503.        }
  504.     return 0;
  505. }
  506.  
  507. #undef lix
  508. #undef liy
  509. #undef litox
  510. #undef litoy
  511.  
  512. /* Add a segment to the path.  This handles all the complex cases. */
  513. private int add_capped(P4(gx_path *, gs_line_cap, int (*)(P3(gx_path *, fixed, fixed)), ep_ptr));
  514. private int
  515. stroke_add(int first, register pl_ptr plp, pl_ptr nplp, gs_state *pgs)
  516. {    gx_path *ppath = stroke_path;
  517.     int code;
  518.     if ( ppath == 0 ) return 0;    /****** strokepath is NYI ******/
  519.     if ( plp->thin )
  520.        {    /* We didn't set up the endpoint parameters before, */
  521.         /* because the line was thin.  Do it now. */
  522.         compute_caps(plp);
  523.        }
  524.     if ( (code = add_capped(ppath, (first == 0 ? pgs->line_params->cap : gs_cap_butt), gx_path_add_point, &plp->o)) < 0 )
  525.         return code;
  526.     if ( nplp == 0 )
  527.        {    code = add_capped(ppath, pgs->line_params->cap, gx_path_add_line, &plp->e);
  528.        }
  529.     else if ( pgs->line_params->join == gs_join_round )
  530.        {    code = add_capped(ppath, gs_cap_round, gx_path_add_line, &plp->e);
  531.        }
  532.     else if ( nplp->thin )        /* no join */
  533.       {    code = add_capped(ppath, gs_cap_butt, gx_path_add_line, &plp->e);
  534.       }
  535.     else                /* join_bevel or join_miter */
  536.        {    gs_fixed_point jp1, jp2;
  537.         /*
  538.          * Set np to whichever of nplp->o.co or .ce
  539.          * is outside the current line.
  540.          * We use the interesting observation that
  541.          * point (x2,y2) is counter-clockwise from (x1,y1)
  542.          * relative to the origin iff x1*y2 < x2*y1.
  543.          * In this case x1,y1 are plp->width,
  544.          * x2,y2 are nplp->width, and the origin is
  545.          * their common point (plp->e.p, nplp->o.p).
  546.          */
  547.         float wx1 = plp->width.x, wy1 = plp->width.y;
  548.         float wx2 = nplp->width.x, wy2 = nplp->width.y;
  549.         int ccw = wx1 * wy2 < wx2 * wy1;
  550.         p_ptr outp, np, np1, np2;
  551.         /* Initialize for a bevel join. */
  552.         jp1.x = plp->e.co.x, jp1.y = plp->e.co.y;
  553.         jp2.x = plp->e.ce.x, jp2.y = plp->e.ce.y;
  554.         if ( ccw )
  555.             outp = &jp2, np2 = np = &nplp->o.co, np1 = &plp->e.p;
  556.         else
  557.             outp = &jp1, np1 = np = &nplp->o.ce, np2 = &plp->e.p;
  558. #ifdef DEBUG
  559. if ( gs_debug['o'] )
  560.         dprintf1("[o]use %s\n", (ccw ? "co (ccw)" : "ce (cw)"));
  561. #endif
  562.         /* Don't bother with the miter check if the two */
  563.         /* points to be joined are very close together, */
  564.         /* namely, in the same square half-pixel. */
  565.         if ( pgs->line_params->join == gs_join_miter &&
  566.              !(fixed2long(outp->x << 1) == fixed2long(np->x << 1) &&
  567.                fixed2long(outp->y << 1) == fixed2long(np->y << 1))
  568.            )
  569.           { /*
  570.              * Check whether a miter join is appropriate.
  571.              * Let a, b be the angles of the two lines.
  572.              * We check tan(a-b) against the miter_check
  573.              * by using the following formula:
  574.              * If tan(a)=u1/v1 and tan(b)=u2/v2, then
  575.              * tan(a-b) = (u1*v2 - u2*v1) / (u1*u2 + v1*v2).
  576.              * We can do all the computations unscaled,
  577.              * because we're only concerned with ratios.
  578.              */
  579.             float u1 = plp->e.cdelta.x, v1 = plp->e.cdelta.y;
  580.             float u2 = nplp->o.cdelta.x, v2 = nplp->o.cdelta.y;
  581.             float num = u1 * v2 - u2 * v1;
  582.             float denom = u1 * u2 + v1 * v2;
  583.             float check = pgs->line_params->miter_check;
  584.             /*
  585.              * We will want either tan(a-b) or tan(b-a)
  586.              * depending on the orientations of the lines.
  587.              * Fortunately we know the relative orientations already.
  588.              */
  589.             if ( !ccw )        /* have plp - nplp, want vice versa */
  590.             num = -num;
  591. #ifdef DEBUG
  592. if ( gs_debug['o'] )
  593.                    {    dprintf4("[o]Miter check: u1/v1=%f/%f, u2/v2=%f/%f,\n",
  594.                  u1, v1, u2, v2);
  595.                         dprintf3("        num=%f, denom=%f, check=%f\n",
  596.                  num, denom, check);
  597.                    }
  598. #endif
  599.             /* Use a miter if num / denom >= check. */
  600.             /* If check >= 0, num < 0 always passes; */
  601.             /* if check < 0, num >= 0 always fails. */
  602.             if ( denom < 0 ) num = -num, denom = -denom;
  603.             if ( check >= 0 ?
  604.             (num < 0 || num >= denom * check) :
  605.             (num < 0 && num >= denom * check)
  606.                )
  607.                {    /* OK to use a miter join. */
  608. #ifdef DEBUG
  609. if ( gs_debug['o'] )
  610.                 dputs("        ... passes.\n");
  611. #endif
  612.                 /* Compute the intersection of */
  613.                 /* the extended edge lines. */
  614.                 line_intersect(outp, &plp->e.cdelta, np,
  615.                            &nplp->o.cdelta, outp);
  616.                }
  617.            }
  618.         if ( (code = gx_path_add_line(ppath, jp1.x, jp1.y)) < 0 ||
  619.              (code = gx_path_add_line(ppath, np1->x, np1->y)) < 0 ||
  620.              (code = gx_path_add_line(ppath, np2->x, np2->y)) < 0 ||
  621.              (code = gx_path_add_line(ppath, jp2.x, jp2.y)) < 0
  622.            )
  623.             return code;
  624.        }
  625.     if ( code < 0 || (code = gx_path_close_subpath(ppath)) < 0 )
  626.         return code;
  627.     return 0;
  628. }
  629.  
  630. /* Routines for cap computations */
  631.  
  632. /* Compute the endpoints of the two caps of a segment. */
  633. private void
  634. compute_caps(register pl_ptr plp)
  635. {    fixed wx2 = plp->width.x;
  636.     fixed wy2 = plp->width.y;
  637.     plp->o.co.x = plp->o.p.x + wx2, plp->o.co.y = plp->o.p.y + wy2;
  638.     plp->o.cdelta.x = -plp->e.cdelta.x,
  639.       plp->o.cdelta.y = -plp->e.cdelta.y;
  640.     plp->o.ce.x = plp->o.p.x - wx2, plp->o.ce.y = plp->o.p.y - wy2;
  641.     plp->e.co.x = plp->e.p.x - wx2, plp->e.co.y = plp->e.p.y - wy2;
  642.     plp->e.ce.x = plp->e.p.x + wx2, plp->e.ce.y = plp->e.p.y + wy2;
  643. #ifdef DEBUG
  644. if ( gs_debug['o'] )
  645.     dprintf4("[o]Stroke o=(%f,%f) e=(%f,%f)\n",
  646.          fixed2float(plp->o.p.x), fixed2float(plp->o.p.y),
  647.          fixed2float(plp->e.p.x), fixed2float(plp->e.p.y)),
  648.     dprintf4("\twxy=(%f,%f) lxy=(%f,%f)\n",
  649.          fixed2float(wx2), fixed2float(wy2),
  650.          fixed2float(plp->e.cdelta.x), fixed2float(plp->e.cdelta.y));
  651. #endif
  652. }
  653.  
  654. /* Add a properly capped line endpoint to the path. */
  655. /* The first point may require either moveto or lineto. */
  656. private int
  657. add_capped(gx_path *ppath, gs_line_cap type,
  658.   int (*add_proc)(P3(gx_path *, fixed, fixed)), /* gx_path_add_point/line */
  659.   register ep_ptr endp)
  660. {    int code;
  661. #define px endp->p.x
  662. #define py endp->p.y
  663. #define xo endp->co.x
  664. #define yo endp->co.y
  665. #define xe endp->ce.x
  666. #define ye endp->ce.y
  667. #define cdx endp->cdelta.x
  668. #define cdy endp->cdelta.y
  669. #ifdef DEBUG
  670. if ( gs_debug['o'] )
  671.     dprintf4("[o]cap: p=(%g,%g), co=(%g,%g),\n",
  672.          fixed2float(px), fixed2float(py),
  673.          fixed2float(xo), fixed2float(yo)),
  674.     dprintf4("[o]\tce=(%g,%g), cd=(%g,%g)\n",
  675.          fixed2float(xe), fixed2float(ye),
  676.          fixed2float(cdx), fixed2float(cdy));
  677. #endif
  678.     switch ( type )
  679.        {
  680.     case gs_cap_round:
  681.        {    fixed xm = px + cdx;
  682.         fixed ym = py + cdy;
  683.         if (    (code = (*add_proc)(ppath, xo, yo)) < 0 ||
  684.             (code = gx_path_add_arc(ppath, xo, yo, xm, ym,
  685.                 xo + cdx, yo + cdy)) < 0 ||
  686.             (code = gx_path_add_arc(ppath, xm, ym, xe, ye,
  687.                 xe + cdx, ye + cdy)) < 0
  688.            ) return code;
  689.        }
  690.         break;
  691.     case gs_cap_square:
  692.         if (    (code = (*add_proc)(ppath, xo + cdx, yo + cdy)) < 0 ||
  693.             (code = gx_path_add_line(ppath, xe + cdx, ye + cdy)) < 0
  694.            ) return code;
  695.         break;
  696.     case gs_cap_butt:
  697.         if (    (code = (*add_proc)(ppath, xo, yo)) < 0 ||
  698.             (code = gx_path_add_line(ppath, xe, ye)) < 0
  699.            ) return code;
  700.        }
  701.     return code;
  702. }
  703.